package org.xiaojinlong;

//import edu.princeton.cs.algs4.StdRandom;
//import edu.princeton.cs.algs4.Stopwatch;

/**
 * @author Jin Long
 *         2015/10/7
 */
public class Test {
    static void fillOneAndZeroThenShuffle(int[] a) {
        int half = a.length / 2;
        for (int i = 0; i < half; i++)
            a[i] = 1;
        for (int i = half; i < a.length; i++)
            a[i] = 0;

        // shuffle
        for (int i = 0; i < a.length; i++) {
//            int r = StdRandom.uniform(i + 1);
            int swap = a[i];
//            a[i] = a[r];
//            a[r] = swap;
        }
    }

    static int[] insertionSort(int[] array) {
        long count = 0;
        if (array.length <= 1) {
            return array;
        }
        else {
            for (int i = 1; i < array.length; i++) {
                int key = array[i];
                int j = i - 1;
                count++;
                while (j >= 0 && array[j] > key) {
                    array[j+1] = array[j];
                    j--;
                    count++;
                }
                array[j+1] = key;
            }
            System.out.println(count + "###");
            return array;
        }
    }

    public static void main(String[] args) {
        int[] a1 = new int[32768];
        fillOneAndZeroThenShuffle(a1);
        int[] a2 = new int[65536];
        fillOneAndZeroThenShuffle(a2);
        int[] a3 = new int[131072];
        fillOneAndZeroThenShuffle(a3);
//        Stopwatch stopwatch = new Stopwatch();
//        double start = stopwatch.elapsedTime();
        insertionSort(a1);
//        double a1T = stopwatch.elapsedTime();
//        System.out1.println((a1T - start) + "###");
        insertionSort(a2);
//        double a2T = stopwatch.elapsedTime();
//        System.out1.println((a2T - a1T) + "###");
        insertionSort(a3);
//        double end = stopwatch.elapsedTime();
//        System.out1.println((end - a2T) + "###");
    }
}
